// 2025/3/31
// https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked
// 最长递增子序列

// 动态规划
class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size(), ans = 0;
            vector<int> dp(n, 1);
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < i; j++)
                {
                    if(nums[j] < nums[i])
                    {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                ans = max(ans, dp[i]);
            }
            return ans;
        }
    };

// 贪心+二分查找
class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size(), len = 1;
            vector<int> d(n + 1, 0);
            d[1] = nums[0];
            for(int i = 1; i < n; i++)
            {
                if(nums[i] > d[len])
                    d[++len] = nums[i];
                else if(nums[i] < d[len])
                {
                    int l = 1, r = len, pos = 0;
                    while(l <= r)
                    {
                        int mid = (l + r) >> 1;
                        if(d[mid] < nums[i])
                        {
                            pos = mid;
                            l = mid + 1;
                        }
                        else
                        {
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            }
            return len;
        }
    };